package demo1;

import java.util.Arrays;
import java.util.List;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    public static void main3(String[] args) {
        //System.out.println(fib(44));

    }

    //斐波那契数列
    //(记忆化搜索)（On）
    public long[] memo = new long[101];
    public int fib(int n) {
        Arrays.fill(memo,-1);
        return (int)dfs(n);
    }

    private long dfs(int n){
        if(memo[n]!=-1) return memo[n];
        if(n<=1) {
            memo[n] = n;
            return n;
        }
        memo[n] = dfs(n-1) + dfs(n-2);
        return memo[n];
    }

    //汉诺塔(递归)
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        int n = A.size();
        hanotaChild(A,B,C,n);
    }

    private void hanotaChild(List<Integer> x, List<Integer> y, List<Integer> z,int n){
        if(n==1){
            z.add(x.remove(x.size()-1));
            return;
        }
        hanotaChild(x,z,y,n-1);
        z.add(x.remove(x.size()-1));
        hanotaChild(y,x,z,n-1);
    }

    //整数替换
    public int integerReplacement(int n) {
        int ret = 0;
        if(n%2==0) {
            while(n!=1){
                n /= 2;
                ret++;
            }
        }else {
            int sum = 1;
            while(sum!=n){
                ret++;
                if(Math.abs(sum-n)==1){
                    sum = n;
                }else{
                    sum *= 2;
                }
            }
        }
        return ret;
    }

    public static void main1(String[] args) {
        int a = -2147483646;
        System.out.println(a);
    }

    public static void main2(String[] args) {
        System.out.println(Integer.MIN_VALUE);
        int[][] arr = {{-2147483646,-2147483645},{2147483646,2147483647}};
        findMinArrowShots(arr);
    }

    //用最少数量的箭引爆气球
    public static int findMinArrowShots(int[][] points) {
        int count = 0;
        int n = points.length;
        Arrays.sort(points,(i,j)->{
            return i[0] > j[0] ? 1 : -1;
        });
        int left = points[0][0]; int right = points[0][1];
        //int min = points[0][1];
        for (int i = 1; i < n; i++) {
            if(right>=points[i][0]){
                count++;
                right = Math.min(right,points[i][1]);
            }else {
                right = points[i][1];
            }
        }
        return n-count;
    }

    //无重叠区间
    public int eraseOverlapIntervals(int[][] intervals) {
        int ret = 0;
        int n = intervals.length;
        Arrays.sort(intervals,(i,j)->{
            return i[0] - j[0];
        });
        int right = intervals[0][1];
        for (int i = 1; i < n; i++) {
            if(right>intervals[i][0]){
                right = Math.min(right,intervals[i][1]);
                ret++;
            }else {
                right = intervals[i][1];
            }
        }

        return ret;
    }
}


























